package algo;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class BipartiteMatcher {

	private static class AnnotatedVertex<T extends Vertex<T>> {
		public T v;
		public int label = 0;
		public AnnotatedVertex<T> prev = null;

		@Override
		public String toString() {
			return v.toString();
		}
		public AnnotatedVertex(T v) {
			this.v = v;
		}

	}

	/**
	 * Finds a bipartite matching for the given set of vertices.
	 * 
	 * @param vertices
	 *            A set of vertices. The vertices must describe a bipartite
	 *            graph.
	 * @return <code>null</code> if all vertices could be matched, otherwise a
	 *         vertex that could not be matched is returned
	 */
	public <T extends Vertex<T>> T getResult(Set<T> vertices) {
		checkPreconditions(vertices);

		Set<AnnotatedVertex<T>> verts = new HashSet<>();
		Map<T, AnnotatedVertex<T>> mapping = new HashMap<T, AnnotatedVertex<T>>();

		for (T v : vertices) {
			AnnotatedVertex<T> annotatedVertex = new AnnotatedVertex<T>(v);
			verts.add(annotatedVertex);
			mapping.put(v, annotatedVertex);
		}

		// start algorithm
		while (true) {
			// find a better path for the matching
			AnnotatedVertex<T> start = null;
			for (AnnotatedVertex<T> v : verts) {
				v.label = -1;
				v.prev = null;
				if (v.v.match == null) {
					start = v;
				}
			}

			if (start == null) {
				// no unmatched node could be found
				break;
			}

			int currentLabel = 0;
			start.label = 0;

			AnnotatedVertex<T> pathEnd = null;
			boolean vertexFound;
			outer: do {
				vertexFound = false;
				for (AnnotatedVertex<T> v : verts) {
					if (v.label == currentLabel) {
						vertexFound = true;
						if (v.v.match == null || mapping.get(v.v.match).label >= 0) {
							// unmatched, label all adjacent vertices
							for (Vertex<T> m : v.v.neighbours) {
								AnnotatedVertex<T> neigh = mapping.get(m);
								if (neigh.label < 0) {
									neigh.prev = v;
									neigh.label = currentLabel + 1;
									if (neigh.v.match == null) {
										// unmatched path end found, an
										// augmented path can be constructed
										pathEnd = neigh;
										break outer;
									}
								}
							}
						} else {
							// only update the spouses label
							AnnotatedVertex<T> n = mapping.get(v.v.match);
							if (n.label < 0) {
								n.prev = v;
								n.label = currentLabel + 1;
							}
						}
					}
				}
				currentLabel++;
			} while (pathEnd == null && vertexFound);

			if (!vertexFound) {
				// no matching for the start node could be established
				return start.v;
			} else {
				// backtrack the augmented path to the start node and switch all
				// matches accordingly
				do {
					AnnotatedVertex<T> prev = pathEnd.prev;
					pathEnd.v.match = prev.v;
					prev.v.match = pathEnd.v;
					pathEnd = prev.prev;
				} while (pathEnd != null);
			}
		}
		return null;
	}

	private <T extends Vertex<T>> void checkPreconditions(Set<T> vertices) {
		for (Vertex<T> v : vertices) {
			if (v.neighbours == null) {
				throw new NullPointerException("No neighbours defined");
			}
			for (Vertex<T> n : v.neighbours) {
				if (n.group == v.group) {
					throw new IllegalArgumentException(
							"Give graph is not bipartite");
				}
				if (!n.neighbours.contains(v)) {
					throw new IllegalArgumentException(
							"Given Graph is not undirected");
				}
			}
			if (v.match != null) {
				throw new IllegalArgumentException("No node must be matched.");
			}
		}
	}
}
